const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定两个链表的头节点，如何找出它们相交的起始节点
// 思路1， 当遍历到链表A的尾节点,继续从链表B的头节点，当遍历到链表B的尾节点继续从链表A的头节点，如果走到相同的节点，返回该节点，否则返回null
function getIntersectionNode(headA, headB) {
    if (headA === null || headB === null) {
        return null
    }
    let curA = headA
    let curB = headB
    while (curA !== curB) {
        curA = curA === null ? headB : curA.next
        curB = curB === null ? headA : curB.next
    }
    return curA
}

// 思路2，如果相交的话，必然从某个节点开始，到后面的节点都是相等的
function getIntersectionNode2(headA, headB) {
    if (headA === null || headB === null) {
        return null
    }
    let sizeA = getLength(headA)
    let sizeB = getLength(headB)
    if (sizeA < sizeB) {
        [headA, headB] = [headB, headA];
        [sizeA, sizeB] = [sizeB, sizeA];
    }
    let i = sizeA - sizeB
    let curA = headA
    let curB = headB
    while (i--) {
        curA = curA.next
    }
    while (curA && curB && curA !== curB) {
        curA = curA.next
        curB = curB.next
    }
    return curA

}

function getLength(head) {
    let count = 0
    let cur = head
    while (cur) {
        count++
        cur = cur.next
    }
    return count
}

let node1 = new ListNode(2)
let node2 = new ListNode(5)
let node3 = new ListNode(1)
let node4 = new ListNode(7)
node1.next = node2
node2.next = node3
node3.next = node4


let node11 = new ListNode(22)
let node22 = new ListNode(55)
let node33 = new ListNode(11)
let node44 = new ListNode(77)
node11.next = node22
node22.next = node33
node33.next = node44
node44.next = node4

console.log(getIntersectionNode(node1, node11))
console.log(getIntersectionNode2(node1, node11))